package demo8;

import lombok.Getter;
import lombok.Setter;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 *
 * a -> ba
 * a-> aab
 * use the hash  deduplicate
 * summary the  quantity of  a  then
 */
public class CompositionDemoWithDups {

    public CompositionDemoWithDups4 createCompositionDemoWithDups4() {
        return new CompositionDemoWithDups4();
    }
    public CompositionDemoWithDups3 createCompositionDemoWithDups3() {
        return new CompositionDemoWithDups3();
    }
    Timer timer = new Timer(true);
    // cons: need use so much memory. for hashSet ,
    @Setter
    @Getter
    public class CompositionDemoWithDups4 {
        AtomicInteger counter = new AtomicInteger(0);
        ArrayList<List<Integer>> allCom = null;
        HashSet<String> set = new HashSet<String>();

        public void composition(String[] arr, int start, int end) {
            reComposition(arr,end - 1, start - 1, arr[0]);
            // collect the list ,and dups the
//            print(list);

        }

        // 0,1,2,3
        private void reComposition(String[] arr,int end, int start, String str) {
            if (start == end) {
                System.out.println(str);
                counter.incrementAndGet();
                return;
            }

            for (int j = 0; j <= str.length(); j++) {
                // "1","0",0
                String newStr = insertChar(arr[(end + 1)] , str, j);
                if(!set.add(newStr)){
                    continue;
                }
                reComposition(arr,end - 1, start, newStr);
            }
        }


        private String insertChar(String dest, String source, int j) {
            // 3 , 0-2
            String start = source.substring(0, j);
            String end = source.substring(j);
            return start + dest + end;
        }

        public void print(List<String> composition) {
            for (int i = 0; i < composition.size(); i++) {
                System.out.println(composition.get(i).toString());
            }
        }
    }

    @Setter
    @Getter
    public class CompositionDemoWithDups3 {
        AtomicInteger counter = new AtomicInteger(0);
        /**2a4b1c
         *
         * make up the func
         * f(2a4b1c) = f(a) + f(1a4b1c)
         *
         * prefix + c
         *
         */
        public void composition(char[] arr) {
            HashMap<Character,Integer> map = makUpFreqTable(arr);
            ArrayList<String> strings = new ArrayList<>();
            permutation(map,arr.length,"",strings);
            System.out.println(" the size of maked up the perms  is: "+strings.size());
            HashSet<String> set = new HashSet<>(strings);
            System.out.println("after deduplication: "+set.size());
            assert set.size()==strings.size();
            print(strings);

        }
        public void permutation(HashMap<Character,Integer> map,int remaining,String prefix,ArrayList<String> strings){
            if(remaining==0){
                strings.add(prefix);
                return;
            }
            Set<Character> characters = map.keySet();
            for (Character character : characters) {
                int count = map.get(character);
                if(count>0){
                    map.put(character,count-1);
                    permutation(map,remaining-1,prefix+character,strings);
                    map.put(character,count);
                }

            }

        }

        private HashMap<Character, Integer> makUpFreqTable(char[] arr) {
            HashMap<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                map.computeIfAbsent(arr[i],(k)->{
                   return 0;
                });
                map.compute(arr[i],(k,v)->{
                   return v+1;
                });
            }
            System.out.println("char count is : "+map.toString());
            return map;
        }


        public void print(List<String> composition) {
            for (int i = 0; i < composition.size(); i++) {
                System.out.println(composition.get(i).toString());
            }
        }
    }
}
